1. Field of the Invention
A production system for an expert system and, more particularly, a method for integrating flow descriptions in a procedural language and production rules is described which simplifies programming. A method for converting such a program into a form executable in conventional production systems is also disclosed.
2. Description of the Prior Art
A representation of conditional knowledge expressed by a form "IF A THEN B" is called a production rule (hereinafter referred to simply as a rule), where A is called a "condition" and B an "action". The condition and the action are related to each other for solving a problem in a given application domain based on an expert's knowledge. A production system, as shown conceptually in FIG. 15, makes inferences based upon a set of rules and performs knowledge processing.
In FIG. 15 the reference numeral 1 indicates a production memory for storing a plurality of rules and numeral 2 indicates a working memory for storing a plurality of working memory elements each composed of a class name and a plurality of attribute values. An inference unit 3 matches the condition parts of all the rules with all of the working memory elements, instantiates and groups those of the rules whose conditions are all satisfied into a conflict set 4, selects one of the rules based on a certain strategy and executes an operation described in the action part of the rule thus selected. Such execution of the action part of a rule is called firing of the rule and firing usually causes a change in the contents of the working memory. The conflict set is produced and the inference processing is repeatedly performed regardless of whether or not the contents of the working memory undergo a change.
FIG. 16 is a flowchart of the above-mentioned operation. In Step 1: a Matching step (ST1), the data (working memory elements) are compared with the condition of each of the rules. Next, in Step 2: a Resolution of conflict step (ST2), a particular rule to be executed is selected. Next, in Step 3: an Execution step (ST3), the selected rule is executed and the data of the working memory is accordingly updated.
Typical production systems obtain desired results by repeatedly performing the above-mentioned steps 1 through 3, while at the same time updating the working memory elements. When no rule is satisfied (i.e. not all of the conditions after "IF" are true) or the action (the part after "THEN") which contains a description stopping the process, however, the production system typically terminates the process regardless of the result.
The condition part of a rule often contains a combination of plural conditions, hereinafter each referred to as a condition element. In creating such a condition, a programmer needs only to list the desired condition elements. In the action part, he only needs to write actions to be executed corresponding to the condition elements in the condition part in the order of their execution. In this context, it is not necessary to write anywhere how to produce the conflict set, that is, how to match the condition parts of the rules with the working memory elements. The reason for this is that the execution sequence of the rules is automatically determined based on an expert knowledge contained in each of the rules, and the selection of one of the rules out of the conflict set is based on a predetermined strategy. For example, the rule having the largest number of condition elements is selected first. Hence, the rules need not be arranged in any predetermined sequence but may be arbitrarily sequenced.
The above is an advantage in the rule base description, allowing much ease in the description of a process for which an ordinary procedural language would incur complex and troublesome programming. However, the idea of the basic production system described above has such drawbacks as follows.
That the rules may be arranged in any sequence means that they are all equal in the possibility of being selected. In practice, however, the situation frequently arises where it is necessary to ignore a particular group of rules or select a rule from a particular group of rules. That is, it is often needed that during execution of a process only rules related thereto be honored as candidates for selection, but in the case of the rule base, it is very difficult for a programmer to select such a particular group of rules arbitrarily and explicitly. In other words, much difficulty is encountered in controlling the selection of rules in a rule base, and it is difficult to collect only those rules for sequentially executing particular processes, for instance, inputting, counting and printing processes (hereinafter referred to as subtasks) and handle them as a module for selection. It is therefore necessary to use a special programming technique in performing a process including a branch or loop with respect to a plurality of subtasks as in the case of the conventional procedural language, and a method called "cluster control", for example, has been employed in the past.
The cluster control is a rule base programming technique in which rules necessary for executing each of several subtasks are defined as a cluster and the name of the cluster to which the rule belongs is described in its condition part. More specifically, a control working memory element is prepared for specifying which cluster is to be executed, and its class name, attribute name and attribute value are defined as, for example, Control, now and Cluster A, respectively. Only those of the rules which have a condition element "& Control now=Cluster A" in their condition part are intended as the candidates for instantiation. This condition element means, "If there exists a working memory element which has the class name `Control` and a value `Cluster A` of the attribute now." Incidentally, only one control working memory element is employed for cluster control, and upon completion of processing in a certain cluster, the attribute value of the control working memory element is updated or changed to the cluster name to be invoked next. Thus, different clusters are selected one after another.
A description will now be given of an example of processing which is performed through utilization of such cluster control.
FIG. 17(a) is a flowchart for executing subtasks A and B in this order and FIG. 17(b) shows rules corresponding thereto. In FIG. 17, reference numerals 5 and 6 indicate the subtasks A and B, and rule names Ar1 to Arn denote rules belonging to a cluster A and Br1 to Brm rules belonging to a cluster B. The rule Ar1 begins with "DEFINE RULE Ar1", identifying the rule name followed by descriptions of a condition part 7 and an action part 8, ending with an "END". The condition part 7 starts with "IF" indicating the beginning of the condition part followed by the condition element "& Control now=Cluster A" indicative of the existence of the working memory element which has the class name "Control", the attribute name " now" and the attribute value "Cluster A", then followed by another condition element "Ac1" denoting a plurality of condition elements in general form, and the condition part 7 ends with an "END". The action part 8 starts with "THEN", followed by a group of actions Ar1 denoting a plurality of actions in general form, terminating with "END". Other rules are also described in the same fashion as mentioned above.
In this example, the letter "A" in "Ar1" indicates the cluster A and "r" stands for a rule, and "c" in "Ac1" and "a" in "Aa1" stand for a condition and an action, respectively. The same applies to other rules.
For a condition element indicating the absence of the working memory element, "?" is used in place of "&" as referred to later on.
For executing a process through use of the rules shown in FIG. 17, a control working memory element is prepared as depicted in FIG. 17(c). Assuming its class name and attribute name are, for instance, "Control" and " now", respectively, if the value of the attribute " now" is the Cluster A, then only rules which have the condition element "& Control now=Cluster A" in their condition part will be the candidates for instantiation, and rules without such a condition element will not be instantiated. On the contrary, where the value of the attribute " now" is the Cluster B, rules which have a condition element "& control now=Cluster B" become the candidates for instantiation, whereas rules without such a condition element will not be instantiated.
In the above example, the condition element "& Control now=Cluster A" is described in the condition part of each of the rules concerning the subtask A, and the condition element "& Control now=Cluster B" is described in the condition part of each of the rules concerning the subtask B. Moreover, in the action part of the rule Arn which is fired at the end of the execution of the subtask A, an action 9 "MODIFY 1 now Cluster B" changes the value of the attribute " now" of the control working memory element to "Cluster B", whereas an action 10 "STOP" described in the action part of the rule Brm is fired at the end of the execution of the subtask B. The numeral immediately following "MODIFY", "1" in this example, indicates the line number of the condition element with which the working memory element updated should match. This method permits omission of the class name of the working memory element whose attribute value is to be updated.
With the programming technique described above with respect to FIG. 17(b), when the initial condition is "& Control now=Cluster A", the attribute value of the control working memory element is updated to Cluster B upon completion of the execution of the cluster A and then the cluster B is executed. Even if the number of clusters is three or more, they can similarly be executed in a sequential order.
FIG. 18(a) is a flowchart including a branch and FIG. 18(b) sets forth the rules corresponding thereto. In FIG. 18(a) reference numeral 11 indicates a process of conditional branch, which is a procedure for selectively executing either one of clusters C12 and D13, depending on whether or not both the condition "& Control now=Cluster J" and a condition Jc1 described in the condition part of each rule of the cluster J are satisfied. Rule names Jr1 and Jr2 denote rules which form the cluster J, and these rules both have the condition "& Control now=Cluster J" in their condition part, but the rule Jr1 has the condition that a condition Jc1 holds as well, whereas the rule Jr2 has the condition that Jc1 does not hold as well.
The execution of the above-mentioned process starts if the initial condition "& Control now=Cluster J" holds, and either the rule Jr1 or Jr2 is fired depending on whether or not a working memory element satisfying the condition Jc1 is present in the working memory.
As a result of this, the process is branched to the cluster C or D for execution, by updating the value of the control working memory element in accordance with the action described in the action part of the rule fired as mentioned above. Rules corresponding to the cluster C12 and D13 and the way they are executed are similar to the example shown in the FIG. 17, and hence no description will be repeated here.
FIG. 19(a) is a flowchart of a process including a loop and FIG. 19(b) shows rules corresponding thereto. In FIG. 19 reference numeral 14 indicates a process of conditional branch for selecting the execution of a cluster E15 or termination of the process depending on whether or not a condition "& Control now=Cluster J" and a condition Jc1 described in the condition part of each rule of the cluster J are satisfied in the production system. Rule names Jr1 and Jr2 denote rules in the cluster J. These rules are similar to those in the case of FIG. 18, and hence no further description will be given of them. A rule Ern is to be fired at the end of the execution of the cluster E. Upon completion of this step, the value of the attribute now of the cluster control working memory element is updated for the cluster J, and then the process returns to the decision step 14.
This step begins with firing the rule Jr1 or Jr2, depending on whether or not a working memory element satisfying the condition Jc1 is present in the working memory, assuming the initial condition "& control now=Cluster J" holds.
As a result of this, in accordance with the action described in the action part of the rule fired as mentioned above, either cluster E is executed by updating the value of the control working memory element, or the process is finished without updating. After execution of the cluster E, the value of the working memory element is updated by "MODIFY 1 now Cluster J". Thus, the decision of the branching condition is repeated, since the looping process is repeated until the branch condition is satisfied.
It is mandatory, however, that the above-described three examples call for a cluster control working memory element which have the class name "Control" and the attribute " now". It is also necessary to include in the condition part of each rule a condition element for cluster control such as "& Control now=Cluster A", in addition to the condition Ac1. Moreover, for executing the cluster B after the cluster A, it is also necessary to describe in the rule to be executed at the end a control action for modifying the value of the attribute " now", such as "MODIFY 1 now Cluster B."
While in the example in FIG. 18(b) the attribute " now" of the cluster control condition has been assumed to take only three values ("Cluster J", "Cluster C" and "Cluster D") for the sake of brevity, a large number of clusters are needed for an actual production system to perform required processes. It is almost impossible in practice to predetermine the order of execution of all clusters used, classify the clusters for each branch or loop, and append a cluster control condition and an action to each rule. In other words, the production system in principle is capable of performing procedural processes through utilization of cluster control, but since there is a limit to man's programming ability, only production systems composed of hundreds to thousands of rules at most have been the largest ever implemented regardless of the scale and capabilities of the computer used. In sum, it has been very difficult to implement large scale production systems which call for complicated sequence control.